PhxPaxos 源码阅读笔记(三):PhxPaxos 设计简介
前置内容:建议对 Paxos 有基本理解后再阅读。
本篇主要是为了后续几篇讲算法实现做些铺垫,个人觉得在看代码之前对设计进行基本的了解是必须的,否则会是一头雾水。
因为只是简介,我只会把 PhxPaxos 中的一些概念稍微讲讲,更为详细的内容还是建议大家阅读微信团队的原文。
我个人感觉 PhxPaxos 的实例-日志-状态机这样的设计是常见的一种实现思路,之前也有向同学请教了一下 X-Paxos 的设计,发现确实很类似,但是各个库出于各自对性能的要求,有着不同的优化取舍罢了(比如 X-Paxos 需要服务一些跨数据中心的高时延场景,所以 Pipelining 是个很好的优化手段)。
实例¶
相信了解过 Paxos 算法的读者都应该知道它最基本的能力:让多个进程(或节点)间达成一致,即它们均确定出同一个值。在确定值后,Paxos 组的成员中只要仍旧有多数派存活,该值将会一直被保持,从而能够容忍部分成员临时断线、掉线重启甚至丢失了该值。
我们知道,由于 Paxos 组内可能有多个 Proposer 同时提案,在达成一致前可能会运行多轮的 Paxos 两阶段协议。PhxPaxos 使用实例来代替了这其中的多轮协议,将多轮 Paxos 协议确定的值称为实例的值。
虽然作为一个 Paxos 库,像 PhxPaxos 这样提供确定一个实例值的能力似乎已经完成基本任务了:它实现了 Paxos 算法,能够确定一个值。
然而,对于一个实际应用而言,光有一个值根本没太多作用,我们往往需要多个值,并且值之间一般也得有关联。因此,PhxPaxos 加入了这种确定多个值的功能,思路很简单,利用多个实例,并且为它们定义很简单的顺序关系,即为每个实例指定一个递增的 ID,依次推进。就如下图所示。
当然,因为网络或者一些其他原因,Paxos 组内的各个成员的实例的进度可能会不同。PhxPaxos 不允许空洞,简单来说就是如果当前多数派的 Acceptor 的实例落后的话,实例将无法被继续推进,必须等到这些落后的实例通过学习机制追赶上来之后,才能够继续推进。我个人感觉这种限制实例递增推进的设计和 Raft 非常类似。
这里略微补充一点关于实例学习的概念。我们知道经典的 Paxos 三角色是 Proposer、Acceptor 以及 Learner。其中的 Learner 就是负责学习追赶它所落后的实例值的,具体我们放到系列的后续篇幅去讲。
日志¶
这里稍微提一下日志是因为这是比实例值更通用的一个说法,尤其在存储系统中。换句话说,在存储系统中,我们通过 Paxos 确定的值实际就是日志,这些日志格式由存储系统设计,并由存储系统去处理。比如说 X-Cluster 是基于 X-Paxos 实现的,它利用 X-Paxos 所确定的就是 MySQL 的 binlog,通过将 Leader 上执行事务得到的 binlog 通过 Paxos 发送到多个副本上应用来实现高可用(这段是个人理解,我对 MySQL 底层并不熟悉,可能会有误,但是思想应该是这样的)。
状态机¶
按照上面所述的设计,现在我们在每个 Paxos 组成员节点上都有了一系列相同并连续有序的日志,下一步就是将这些日志变得更加有意义了,于是引入了状态机。
状态机的作用是应用日志,通过输入日志,不断地进行状态转换。下图是一个 Key-Value 状态机以及它应用日志的过程。
左边是一个个状态,右边是通过日志进行的状态转换,显然,只要各个节点的日志是一致的,它们得到的状态机最终也会是相同的。
检查点¶
在实际场景中,日志是很占空间的,稍微试想一下,存储内容是通过日志确认得到的,那么完全可能有这样的情况:日志比最终应用日志后得到的存储状态还要占用空间的。比如说利用 Paxos 来实现一个文件系统,那么添加 N 个不同文件产生的日志大小基本上是会大于存储这 N 个文件的空间的,这大概也是 Paxos 很少直接应用在文件系统的存储节点之间的原因(更多用于协调节点)。
总之,日志会占用空间并且可能还不小。而从之前描述的设计可以看到,如果 Paxos 组内加入一个全新的成员,它想到追赶到和大家一致的状态的话,是需要所有的日志的。所以,检查点被引入以解决这种不留日志没法恢复、留了日志空间占用过大的问题。
检查点实质上就是对状态机做快照,因为快照表现的是当前状态,所以相比于为了达到此状态需要应用的所有日志,它可能是不大的。比如说 Redis 的 RDB 文件就可以视作是对 Redis 的一个检查点,它其中就成功地压缩了很多针对同一个键值的操作。
在检查点的帮助下,一个新成员的追赶就变成了应用检查点加上应用该检查点之后的日志。
结语¶
我个人感觉 PhxPaxos 基本上改成了 Raft,起码在理解难度上差不太多了,虽然像 Leader 选举这样的功能对 PhxPaxos 而言是可选的。不过也可能是我的错觉,毕竟没细看过 Raft 的所有内容。
在对设计进行简单的介绍后,接下来就是对 PhxPaxos 的算法实现部分进行剖析了,不过后面好像会更忙,更新嘛。。尽量一周能出一篇。